1884C - Medium Design - CodeForces Solution

// SPDX-License-Identifier: 0BSD
// MOTD: listen to https://soundcloud.com/gingaloid ok thanks bye
// e.g. https://soundcloud.com/gingaloid/shutup
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#include <bits/stdc++.h>
#ifdef LOCAL
  #include "lib/local.hpp"
#else
  #define VDBG(...)
  #define DBG(...)
  #define endl '\n' // remove this line for interactive tasks
  #undef assert
  #define assert(expr) (expr) || (__builtin_unreachable(), 0)
#endif
#define FORT(T, I, S, N) for(T I = (S); I < (N); ++I)
#define RFORT(T, I, S, N) for(T I = (S); I > (N); --I)
#define FOR(I, S, N) FORT(ptrdiff_t, I, (S), (N)) // ptrdiff_t = basically same as isize in rust
#define RFOR(I, S, N) RFORT(ptrdiff_t, I, (S), (N))
#define FORI(N) FOR(i, 0, (N))
#define FORJ(N) FOR(j, 0, (N))
#define FORK(N) FOR(k, 0, (N))
#define RFORI(N) RFOR(i, (N)-1, -1)
#define RFORJ(N) RFOR(j, (N)-1, -1)
#define SPOON(N) RFOR(k, (N)-1, -1)
#define ALL(X) (X).begin(), (X).end()
#define RALL(X) (X).rbegin(), (X).rend()
#define RD(T, X...) T X; rd(X);
#define FN [&]
#define CMP(T, lhs, rhs) FN(const T &lhs, const T &rhs)
#define  A auto
#define _T template
#define _Y typename
#define _SP(A,B,C) bool f=!0;for(A){if(f){f=!1;}else{B;}C;}
#define _I1(C) _T<_Y T>ostream&operator<<(ostream&o,C<T>const&v){_SP(const A&x:v,o<<' ',o<<x)return o;}_T<_Y T>istream&operator>>(istream&i,C<T>&v){for(A&x:v){i>>x;}return i;}
#define _I2(C) _T<_Y T,_Y Y>ostream&operator<<(ostream&o,C<T,Y>const&v){_SP(const auto&x:v,o<<endl,o<<x.first<<' '<<x.second)return o;}
using namespace std;constexpr long double PI=3.1415926535897932384626433832795029L;_T<_Y T>using V=vector<T>;_T<_Y T,_Y Y>using P=pair<T,Y>;_T<_Y T,size_t S>using Ar=array<T, S>;_T<_Y T>using pq_big_1st=priority_queue<T>;_T<_Y T>using pq_small_1st=priority_queue<T,V<T>,greater<T>>;using i64=int64_t;using u64=uint64_t;using ll=i64;using i32=int32_t;using u32=uint32_t;using I=i32;using i16=int16_t;using u16=uint16_t;using i8=int8_t;using u8=uint8_t;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());const char*YN(bool b){return b?"YES":"NO";}_T<_Y T,_Y Y>bool umin(T&a,const Y&b){return b<a&&(a=b,!0);}_T<_Y T,_Y Y>bool umax(T&a,const Y&b){return b>a&&(a=b,!0);}_T<_Y T,_Y Y>ostream&operator<<(ostream&o,pair<T,Y>const&p){return o<<p.first<<' '<<p.second;}_T<_Y T,_Y Y>istream&operator>>(istream&i,pair<T,Y>&p){return i>>p.first>>p.second;}_T<_Y T,size_t N>ostream&operator<<(ostream&o,array<T,N>const&v){_SP(const A&x:v,o<<' ',o<<x)return o;}_T<_Y T,size_t N>istream&operator>>(istream&i,array<T,N>&v){for(A&x:v){i>>x;}return i;}_I1(V);_I1(set);_I1(multiset);_I1(unordered_set);_I1(unordered_multiset);_I1(deque);_I1(queue);_I2(map);_I2(multimap);_I2(unordered_map);_I2(unordered_multimap);_T<size_t S=0,_Y...T>struct _Tio{static inline void i(istream&i,tuple<T...>&t){if constexpr(S<sizeof...(T)){i>>get<S>(t);_Tio<S+1,T...>::i(i,t);}}static inline void o(ostream&o,tuple<T...>const&t){if constexpr(S<sizeof...(T)){if constexpr(S)o<<' ';o<<get<S>(t);_Tio<S+1,T...>::o(o,t);}}};_T<_Y...T>istream&operator>>(istream&i,tuple<T...>&t){return _Tio<0,T...>::i(i,t),i;}_T<_Y...T>ostream&operator<<(ostream&o,tuple<T...>&t){return _Tio<0,T...>::o(o,t),o;}_T<_Y...S>inline void rd(S&...a){A t=forward_as_tuple(a...);cin>>t;}_T<_Y T>inline T read(){if constexpr(is_same<T,bool>::value)return read<char>();T x;if constexpr(is_same<T,V<bool>>::value){string s;cin>>s;x.resize(s.size());FORI(s.size())x[i]=s[i]!='0';}else cin>>x;return x;}_T<_Y T>inline V<T>read(size_t n){V<T>v(n);FORI(n)if constexpr(is_same<T,bool>::value)v[i]=read<T>();else cin>>v[i];return v;}_T<_Y...S>inline void pr2(const S&...a){(cout<<...<<a);}_T<_Y...S>inline void pr2n(const S&...a){(cout<<...<<a)<<endl;}_T<_Y...S>inline void pr(const S&...a){A t=forward_as_tuple(a...);cout<<t;}_T<_Y...S>inline void prn(const S&...a){pr(a...);cout<<endl;}_T<_Y...S>inline void epr(const S&...a){A t=forward_as_tuple(a...);cerr<<t<<' ';}_T<_Y...S>inline void eprn(const S&...a){epr(a...);cerr<<endl;}

template<typename T> struct Lst {
  constexpr static T ZERO = 0;
  static void op(T &a, const T &b) { a += b; }
  struct Elem { I l = 0, r = 0; T x = ZERO; };
  vector<Elem> v; size_t n;
  Lst(size_t n) : n(n<=1 ? n : (2 << __lg(n-1))) { alloc(); }
  inline size_t alloc() { v.push_back(Elem()); return v.size() - 1; }
  void _add(I w, size_t n, size_t i, size_t j, T x) {
    if (i == 0 && j == n) { op(v[w].x, x); return; }
    auto m = n/2;
    if (i < m) {
      if (!v[w].l) v[w].l = alloc();
      _add(v[w].l, m, i, min(j, m), x);
    }
    if (j > m) {
      if (!v[w].r) v[w].r = alloc();
      _add(v[w].r, m, max(i,m)-m, j-m, x);
    }
  }
  void add(size_t i, size_t j, const T &x) { return _add(0, n, i, j, x); }
  T get(size_t i) { return _get(v[0], n, i, i+1); }
  T get(size_t i, size_t j) { return _get(v[0], n, i, j); }
  T _get(const Elem &w, size_t n, size_t i, size_t j) const {
    T ret = w.x;
    auto m = n/2;
    if (i < m && w.l) op(ret, _get(v[w.l], m, i, min(j, m)));
    if (j > m && w.r) op(ret, _get(v[w.r], m, max(i,m)-m, j-m));
    return ret;
  }
};

void solve() noexcept {
  RD(I, n, m);
  A v = read<P<I,I>>(n);
  // maximize max(arr) - min(arr)
  // 
  Lst<I> s(m), c0(m), cm(m);
  FORI(v.size()) s.add(--v[i].first, --v[i].second+1, 1);
  FORI(v.size()) if (v[i].first == 0) c0.add(v[i].first, v[i].second+1, 1);
  FORI(v.size()) if (v[i].second == m-1) cm.add(v[i].first, v[i].second+1, 1);
  set<I> points{0,m-1};
  // better to stack all on one side
  // so for each point
  // if leftmost seg over it isn't 0 or rightmost isn't m-1: win
  // otherwise, i will get min(val - count_overlapping(0), val - count_overlapping(m-1))
  // so for each val, i need to know how many segs overlap it and 0 and m-1
  FORI(v.size()) points.insert(v[i].first);
  I maxv = 0;
  for (A p : points) {
    I ans = s.get(p);
    ans -= min(c0.get(p), cm.get(p));
    umax(maxv, ans);
  }
  prn(maxv);
}

int main() {ios_base::sync_with_stdio(!1);cin.tie(0);cout.tie(0);cout<<fixed<<setprecision(15);srand(chrono::steady_clock::now().time_since_epoch().count());
  RD(I, t);
  FORI(t) solve();
}